#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 100 + 5;
char buf[maxn]; //输入产生式
int n;          //产生式的数量
class node
{
public:
    string left;       //产生式左部
    set<string> right; //产生式右部
    node(const string &str)
    {
        left = str;
        right.clear();
    }
    void push(const string &str)
    {
        right.insert(str);
    }
    void print()
    {
        printf("%s->", left.c_str());
        set<string>::iterator it = right.begin();
        printf("%s", it->c_str());
        it++;
        for (; it != right.end(); it++)
            printf("|%s", it->c_str());
        cout << endl;
    }
};
map<string, int> mp; //记录每个node的下标
vector<node> vnode;  //每一个产生式
string start;        //文法G[s]
bool used[maxn];     //用于去掉无用产生式
//初始化工作
void init()
{
    mp.clear();
    vnode.clear();
    start = "S";
}
//消除间接左递归
void eliminateIndirectLeftRecursion()
{
    for (int i = 0; i < vnode.size(); i++)
    {
        for (int j = 0; j < i; j++)
        {
            vector<string> ans;
            set<string> &righti = vnode[i].right;
            set<string> &rightj = vnode[j].right;
            char ch = vnode[j].left[0]; //取所有Aj产生式的左部的非终结符
            set<string>::iterator iti, itj;
            for (iti = righti.begin(); iti != righti.end(); iti++)
            {
                if (iti->at(0) == ch) //如果当前产生式右部的非终结符和Aj相同
                    for (itj = rightj.begin(); itj != rightj.end(); itj++)
                        ans.push_back(*itj + iti->substr(1)); //进行替换操作,先存储起来
            }
            while (!righti.empty())
            {
                if (righti.begin()->at(0) != ch) //存储当前没有替换的产生式右部
                    ans.push_back(*righti.begin());
                righti.erase(righti.begin()); //被替换过的产生式右部也删除掉
            }
            for (int k = 0; k < ans.size(); k++) //将替换过的产生式右部进行更新操作
                righti.insert(ans[k]);
        }
    }
    cout << "消除间接左递归后的结果：" << endl;
    for (int k = 0; k < vnode.size(); k++)
        vnode[k].print();
    cout << endl;
}
//消除直接左递归
void eliminateDirectLeftRecursion()
{
    for (int i = 0; i < vnode.size(); i++)
    {
        char ch = vnode[i].left[0];
        set<string> &right = vnode[i].right; //拿到当前右部
        set<string>::iterator it;
        string tmp = vnode[i].left.substr(0, 1) + "\'"; //对非终结符更改
        bool flag = true;
        for (it = right.begin(); it != right.end(); it++)
        {
            if (it->at(0) == ch)
            {
                vnode.push_back(node(tmp));
                mp[tmp] = vnode.size();
                flag = false;
                break;
            }
        }
        int idx = mp[tmp] - 1;
        if (flag)
            continue; //对于非终结符不相同的产生式我们需要跳过
        vector<string> ans;
        set<string> &tmpSet = vnode[idx].right;
        tmpSet.insert("~"); //添加空字符
        while (!right.empty())
        {
            if (right.begin()->at(0) == ch)
                tmpSet.insert(right.begin()->substr(1) + tmp);
            else
                ans.push_back(right.begin()->substr(0) + tmp);
            right.erase(right.begin()); //删除掉原本产生式右部
        }
        for (int k = 0; k < ans.size(); k++)
            right.insert(ans[k]); //更新加入新的产生式右部
    }
    cout << endl;
    cout << "消除直接左递归后的结果：" << endl;
    for (int k = 0; k < vnode.size(); k++)
        vnode[k].print();
    cout << endl;
}
//搜索
void dfs(int x)
{
    if (used[x])
        return;
    used[x] = 1; //将当前下标记录
    set<string>::iterator it = vnode[x].right.begin();
    for (; it != vnode[x].right.end(); it++)
    {
        for (int i = 0; i < it->length(); i++)
        {
            if (isupper(it->at(i)))
            {                                                      //判断是否是大写字母
                if (i + 1 < it->length() && it->at(i + 1) == '\'') //如果当前是替换的那个字符
                    dfs(mp[it->substr(i, 2)] - 1);
                else
                    dfs(mp[it->substr(i, 1)] - 1);
            }
        }
    }
}
//去掉无用产生式
void removeUselessProduction()
{
    memset(used, 0, sizeof(used));
    int idx = mp[start] - 1;
    dfs(idx); //搜索
    cout << "最终文法：" << endl;
    vector<node> res;
    for (int i = 0; i < vnode.size(); i++)
        if (used[i]) //存储已经标记过的产生式
            res.push_back(vnode[i]);
    vnode.clear();
    vnode = res;
}
int main()
{
    cout << "请输入文法G[S]的产生式数量：" << endl;
    while (cin >> n)
    {
        init(); //初始化
        getchar();
        cout << "依次输入文法G[S]的产生式：" << endl;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", buf); //输入产生式
            int len = strlen(buf), j;
            for (j = 0; j < len; j++)
                if (buf[j] == '-')
                {
                    buf[j] = 0; //进行左部和右部切分
                    break;
                }
            string tmp = buf; //拿到产生式的左部
            if (!mp[buf])
            {
                vnode.push_back(node(tmp));
                mp[tmp] = vnode.size();
            }
            int idx = mp[tmp] - 1; //获取左部的下标
            tmp = buf + j + 2;     //拿到产生式的右部
            vnode[idx].push(tmp);
        }
        //确定开始节点
        int idx = vnode.size() - 1;
        start = vnode[idx].left[0];
        eliminateIndirectLeftRecursion(); //消除间接左递归
        eliminateDirectLeftRecursion();   //消除直接左递归
        removeUselessProduction();        //去掉无用产生式
        /*
         *test
         */
        /*cout<<"---------test---------"<<endl;
        for(int k=0;k<vnode.size();k++)
            vnode[k].print();*/
        for (int k = 0; k < vnode.size(); k++)
            vnode[k].print();
    }
    return 0;
}
